// m

// 给定一个只包含0、1元素的二维数组，1代表岛屿，0代表水，一座岛的面积就是上下左右相邻的1所组成的连通块的数目
// 计算最大的岛屿面积

// 解题思路
// 思路1： 深度优先搜索
// 1.遍历二维数组中的每一个元素，对于每个值为1的元素：
//    1. 将该位置上的值置位0（防止二次重复计算）
//    2. 递归搜索该位置上下左右四个位置，并统计搜到值为1的元素个数
//    3. 返回值为1的元素个数（即为该岛的面积）
// 2. 维护并更新最大的岛屿面积
// 3. 返回最大的岛面积

// 复杂度分析
// 时间复杂度：O(m * n)， m和n分别为行数和列数
// 空间复杂度：O(m * n)

function maxAreaOfIsland(grid) {
    function dfs(grid, i, j) {
        let n = grid.length
        let m = grid[0].length
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] === 0) {
            return 0
        }
        let ans = 1
        grid[i][j] = 0
        ans += dfs(grid, i + 1, j)
        ans += dfs(grid, i, j + 1)
        ans += dfs(grid, i - 1, j)
        ans += dfs(grid, i, j - 1)
        return ans
    }
    let ans = 0
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 1) {
                ans = Math.max(ans, dfs(grid, i, j))
            }
        }
    }
    return ans
}

// 思路2：广度优先搜索
// 1. 使用ans记录最大岛屿面积
// 2. 遍历二维数组中的每个元素，对于每个值为1的元素
//      1. 将该元素置为0， 并使用队列q存储该节点位置，使用temp_ans记录当前岛屿面积
//      2. 然后从队列q中取出第一个节点位置(i, j)，遍历该节点位置上下左右四个方向的相邻节点，并将其置为0
//         并将其加入到队列中，并累加到当前岛屿面积
//      3. 不断重复上一步骤，直到队列q为空
//      4. 更新当前最大岛屿面积，即ans = max(ans, temp_ans)

function maxAreaOfIsland(grid) {
    let directs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    let rows = grid.length
    let cols = grid[0].length
    let ans = 0
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 1) {
                grid[i][j] = 0
                let temp_ans = 1
                let q = [[i, j]]
                while (q.length) {
                    let [i, j] = q.shift()
                    for (let k = 0; k < directs.length; k++) {
                        let new_i = i + directs[k][0];
                        let new_j = j + directs[k][1]
                        if (new_i < 0 || new_i >= rows || new_j < 0 || new_j >= cols || grid[new_i][new_j] === 0) {
                            continue
                        }
                        grid[new_i][new_j] = 0
                        q.push([new_i, new_j])
                        temp_ans += 1
                    }
                }
                ans = Math.max(ans, temp_ans)
            }
        }
    }
    return ans
}

let grid = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 1]
]

console.log(maxAreaOfIsland(grid));